//
// Created by shenbin on 2022/4/18.
// https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
// 单调栈
//

#ifndef ALGORITHM_TRAINNING_C03_LC84_H
#define ALGORITHM_TRAINNING_C03_LC84_H

#include <vector>
#include <stack>

using namespace std;

class LeetCode84 {
public:
    int largestRectangleArea(vector<int> &heights) {
        int ans = 0;
        for (int height: heights) {
            int accumulatedWidth = 0;
            while (!s.empty() && s.top().height >= height) {
                accumulatedWidth += s.top().width;
                ans = max(ans, s.top().height * accumulatedWidth);
                s.pop();
            }
            s.push({accumulatedWidth + 1, height});
        }
        return ans;
    }

private:
    struct Rect {
        int width;
        int height;
    };
    stack<Rect> s;

};

#endif //ALGORITHM_TRAINNING_C03_LC84_H
